11288. Пары из людей

На вечеринке присутствует n людей. Каждый человек может присоединиться к танцу в одиночку или в паре с любым другим. Найдите количество различных способов, которыми все n человек могут присоединиться к танцу.

Вход. Одно целое число n (1 ≤ n ≤ 10⁵).

Выход. Выведите количество различных способов, которыми все n человек могут присоединиться к танцу. Выведите ответ по модулю 10⁹ + 7.

Пример входа	Пример выхода
3	4

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть f(n) – количество различных способов, которыми все n человек могут присоединиться к танцу. Например,

· f(1) = 1, один человек танцует сам;

· f(2) = 2, так как для двух человек имеется два варианта: либо танцевать по отдельности, либо в паре;

Рассмотрим n-го человека:

· Если он танцует отдельно, то остальные n – 1 человек могут присоединиться к танцу f(n – 1) способами.

· n-ый человек может взять себе в пару любого из n – 1 людей. Остальные n – 2 человек могут присоединиться к танцу f(n – 2) способами.

Таким образом имеем соотношение:

f(n) = f(n – 1) + (n – 1) * f(n – 2)

Пример

Пусть имеется n = 3 людей. Они могут присоединиться к танцу 4 способами:

· если третий человек танцует отдельно: {1, 2, 3}, {{1, 2}, 3};

· если третий человек танцует в паре: {1, {2, 3}}, {2, {1, 3}}.

Вычислим f(3) по формуле:

f(3) = f(2) + 2 * f(1) = 2 + 2 * 1 = 4

Реализация алгоритма

Объявим модуль и массив для хранения результатов: dp[n] = f(n).

#define MOD 1000000007

long long dp[100001];

Читаем входное значение n.

scanf("%d", &n);

Последовательно вычисляем значения f(1), f(2), …, f(n), запоминая результаты в массиве dp.

dp[1] = 1; dp[2] = 2;

for (i = 3; i <= n; i++)

dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD;

Выводим ответ.

printf("%lld\n", dp[n]);

Python реализация

Объявим модуль MOD, по которому будут производиться вычисления.

MOD = 1000000007

Читаем входное значение n.

n = int(input())

Объявим список для хранения результатов: dp[n] = f(n).

dp = [0] * (n + 1)

Последовательно вычисляем значения f(1), f(2), …, f(n), запоминая результаты в списке dp.

dp[1] = 1

if n > 1: dp[2] = 2

for i in range(3, n + 1):

dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD

Выводим ответ.

print(dp[n])